Grokking Oracle Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Oracle Easy
Count Number of Pairs With Absolute Difference K (easy)
Solution: Count Number of Pairs With Absolute Difference K
Degree of an Array (easy)
Solution: Degree of an Array
Find Subsequence of Length K With the Largest Sum (easy)
Solution: Find Subsequence of Length K With the Largest Sum
Rectangle Overlap (easy)
Solution: Rectangle Overlap
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Island Perimeter (easy)
Solution: Island Perimeter
Climbing Stairs (easy)
Solution: Climbing Stairs
Move Zeroes (easy)
Solution: Move Zeroes
Excel Sheet Column Title (easy)
Solution: Excel Sheet Column Title
Valid Parentheses (Easy)
Solution: Valid Parentheses
Oracle Medium
Longest Palindromic Substring (medium)
Solution: Longest Palindromic Substring
Single Element in a Sorted Array (medium)
Solution: Single Element in a Sorted Array
Pairs of Songs With Total Durations Divisible by 60 (medium)
Solution: Pairs of Songs With Total Durations Divisible by 60
Search a 2D Matrix II (medium)
Solution: Search a 2D Matrix II
Minimize Maximum of Array (medium)
Solution: Minimize Maximum of Array
Asteroid Collision (medium)
Solution: Asteroid Collision
Combination Sum (medium)
Solution: Combination Sum
Binary Tree Right Side View (medium)
Solution: Binary Tree Right Side View
Sort Colors (medium)
Solution: Sort Colors
Group Anagrams (Medium)
Solution: Group Anagrams
Decode String (Medium)
Solution: Decode String
Number of Islands (medium)
Solution: Number of Islands
Binary Tree Zigzag Level Order Traversal (medium)
Solution: Binary Tree Zigzag Level Order Traversal
Longest Common Subsequence (medium)
Solution: Longest Common Subsequence
Rotting Oranges (medium)
Solution: Rotting Oranges
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Delete Node in a BST (medium)
Solution: Delete Node in a BST
Remove Duplicate Letters (medium)
Solution: Remove Duplicate Letters
Longest Substring Without Repeating Characters (medium)
Solution: Longest Substring Without Repeating Characters (medium)
Search in Rotated Array (medium)
Solution: Search in Rotated Array
Spiral Matrix (medium)
Solution: Spiral Matrix
Container With Most Water (Medium)
Solution: Container With Most Water
3Sum (medium)
Solution: 3Sum
Simplify Path (medium)
Solution: Simplify Path
Next Permutation (medium)
Solution: Next Permutation
Basic Calculator II (medium)
Solution: Basic Calculator II
Merge Intervals (medium)
Solution: Merge Intervals
Restore IP Addresses (medium)
Solution: Restore IP Addresses
Longest Increasing Subsequence (medium)
Solution: Longest Increasing Subsequence
Validate Binary Search Tree (medium)
Solution: Validate Binary Search Tree
Integer to English Words (hard)
Solution: Integer to English Words
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Merge K Sorted Lists (hard)
Solution: Merge K Sorted Lists
Max Points on a Line (hard)
Solution: Max Points on a Line
Sudoku Solver (hard)
Solution: Sudoku Solver
Longest Valid Parentheses (hard)
Solution: Longest Valid Parentheses
Remove Nth Node From End of List (Medium)
Solution: Remove Nth Node From End of List
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Constrained Subsequence Sum (hard)
Solution: Constrained Subsequence Sum
Solution: Merge Intervals

Problem Statement

Given a list of intervals, merge all the overlapping intervals to produce a list that has only mutually exclusive intervals.

Example 1:

Intervals: [[1,4], [2,5], [7,9]]
Output: [[1,5], [7,9]]
Explanation: Since the first two intervals [1,4] and [2,5] overlap, we merged them into one [1,5].
Image

Example 2:

Intervals: [[6,7], [2,4], [5,9]]
Output: [[2,4], [5,9]]
Explanation: Since the intervals [6,7] and [5,9] overlap, we merged them into one [5,9].

Example 3:

Intervals: [[1,4], [2,6], [3,5]]
Output: [[1,6]]
Explanation: Since all the given intervals overlap, we merged them into one.

Constraints:

  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104

Solution

Let’s take the example of two intervals (ā€˜a’ and ā€˜b’) such that a.start <= b.start. There are four possible scenarios:

Image

Our goal is to merge the intervals whenever they overlap. For the above-mentioned three overlapping scenarios (2, 3, and 4), this is how we will merge them:

Image

To solve this problem, we will sort the list of intervals by their start times. This helps in easily identifying overlapping intervals. After sorting, we can iterate through the intervals, merging them if they overlap. We will maintain a list to store the merged intervals. As we iterate, we compare the current interval with the last interval in the merged list. If they overlap, we merge them by extending the end time. Otherwise, we add the current interval to the merged list.

This approach works because sorting brings overlapping intervals next to each other. This allows us to handle overlapping intervals in a single pass through the list. Sorting the intervals first is key to simplifying the merging process.

Step-by-Step Algorithm

  1. Sort Intervals:

    • Begin by sorting the list of intervals based on their start times.
    • This can be done using a comparator in Java.
  2. Initialize Merged List:

    • Create an empty list called mergedIntervals to store the merged intervals.
  3. Set Initial Interval:

    • Start by picking the first interval and set it as the current interval.
  4. Iterate Through Intervals:

    • Loop through the rest of the intervals.
    • For each interval:
      • Check Overlap:
        • If the start of the current interval is less than or equal to the end of the previous interval, it means they overlap.
        • In this case, merge them by updating the end of the previous interval to be the maximum of both ends.
      • Non-overlapping:
        • If they do not overlap, add the previous interval to the mergedIntervals list.
        • Update the current interval to be the next interval in the list.
  5. Add Last Interval:

    • After the loop completes, add the last interval to the mergedIntervals list.
  6. Return Result:

    • Return the mergedIntervals list as the final output.

Algorithm Walkthrough

Given input: [[1, 4], [2, 5], [7, 9]]

  1. Sort Intervals:

    • Original intervals: [[1, 4], [2, 5], [7, 9]]
    • Sorted intervals: [[1, 4], [2, 5], [7, 9]] (already sorted)
  2. Initialize Merged List:

    • mergedIntervals: []
  3. Set Initial Interval:

    • Current interval: [1, 4]
  4. Iterate Through Intervals:

    • First Iteration:
      • Next interval: [2, 5]
      • Check overlap: 2 <= 4 (True)
      • Merge intervals: [1, 5]
      • Update current interval: [1, 5]
    • Second Iteration:
      • Next interval: [7, 9]
      • Check overlap: 7 <= 5 (False)
      • Add previous interval to mergedIntervals: [[1, 5]]
      • Update current interval: [7, 9]
  5. Add Last Interval:

    • Add last interval to mergedIntervals: [[1, 5], [7, 9]]
  6. Return Result:

    • mergedIntervals: [[1, 5], [7, 9]]
Image

Code

Here is what our algorithm will look like:

Java

. . . .

Time Complexity

The time complexity of the above algorithm is , where ā€˜N’ is the total number of intervals. We are iterating the intervals only once which will take O(N), in the beginning though, since we need to sort the intervals, our algorithm will take .

Space Complexity

The space complexity of the above algorithm will be O(N) as we need to return a list containing all the merged intervals. We will also need O(N) space for sorting. For Java, depending on its version, Collections.sort() either uses Merge sort or Timsort, and both these algorithms need O(N) space. Overall, our algorithm has a space complexity of O(N).

Similar Problems

Problem 1: Given a set of intervals, find out if any two intervals overlap.

Example:

Intervals: [[1,4], [2,5], [7,9]]
Output: true
Explanation: Intervals [1,4] and [2,5] overlap

Solution: We can follow the same approach as discussed above to find if any two intervals overlap.

Merge Intervals (medium)
Restore IP Addresses (medium)
Mark as Completed

On this page

Problem Statement

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Similar Problems